package 典型.贪心算法;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Classname IntervalScheduling
 * @Description TODO
 * @Date 2021/4/22 0:24
 * @Created by yin
 */
public class IntervalScheduling {
    public int intervalSchedule(int[][] intvs) {
        if (intvs.length == 0) return 0;
        Arrays.sort(intvs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1]; // end升序排列
            }
        });
        int count = 1; //至少有一个区间
        int x_end = intvs[0][1];
        for (int[] interval : intvs) {
            int start = interval[0];
            if (start >= x_end) {
                count++;
                x_end = interval[1];
            }
        }
        return count;
    }
}
